//�ַ���ת������

package Leetcode;

import java.util.HashMap;
import java.util.Map;

class solution_008 {
	public int myAtoi(String s) {
		int begin = 0; // ��ʾ�Ƿ�ʼ��ȡ����
		int sign = 1; // ��ʾ���ս��������
		long result = 0;
		for (char c : s.toCharArray()) {
			// ȥ���ȵ��ո�ע��begin=0��Ȼ��ȥ���м�Ŀո�
			if (c == ' ' & begin == 0)
				continue;
			if (begin == 0) {
				if (c == '+') {
					// ��һ��Ϊ+
					begin = 1;
					continue;
				} else if (c == '-') {
					// ��һ��Ϊ-
					begin = 1;
					sign = -sign;
					continue;
				} else if (c <= '9' & c >= '0') {
					// ��һ��Ϊ����
					begin = 1;
					result = 10 * result + (c - '0');
				} else {
					// ��һ��Ϊ��ĸ
					return 0;
				}
			} else {
				if (c <= '9' & c >= '0') {
					result = 10 * result + (c - '0');
					// ��ÿ�ζ�������ʱ�ж��Ƿ�Խ��
					long temp = result * sign;
					if (temp > Math.pow(2, 31) - 1) {
						return (int) (Math.pow(2, 31) - 1);
					}

					if (temp < -Math.pow(2, 31)) {
						return (int) (-Math.pow(2, 31));
					}
				} else {
					break;
				}
			}
		}
		// ������result��������ж��Ƿ�Խ����Ϊ�������յ����long����Ҳ�޷�����
		return (int) (result * sign);
	}
}

// �𰸸����뷨��ʹ���Զ���
//			' '	    +/-		number		other
//start		start	signed	in_number	end
//signed	end		end		in_number	end
//in_number	end		end		in_number	end
//end		end		end		end			end

public class Solution008 {
	public static void main(String[] args) {
		String s = "  aa  ";
		String ss = s.trim();
		System.out.println(ss);
	}

	class Automaton {
		public int sign = 1;
		public long result = 0;
		private String state = "start";
		private Map<String, String[]> table = new HashMap<String, String[]>() {
			{
				put("start", new String[] { "start", "signed", "in_number", "end" });
				put("signed", new String[] { "end", "end", "in_number", "end" });
				put("in_number", new String[] { "end", "end", "in_number", "end" });
				put("end", new String[] { "end", "end", "end", "end" });
			}
		};

		private int judge(char c) {
			if (c == ' ')
				return 0;
			else if (c == '+' | c == '-')
				return 1;
			else if (Character.isDigit(c))
				return 2;
			else
				return 3;
		}

		public void get(char c) {
			state = table.get(state)[judge(c)];
			if (state.equals("in_number")) {
				result = result * 10 + (c - '0');
				result = sign == 1 ? Math.min(result, (long) Integer.MAX_VALUE)
						: Math.min(result, -(long) Integer.MIN_VALUE);
			} else if (state.equals("signed")) {
				sign = c == '+' ? 1 : -1;
			}
		}

	}

	public int myAtoi(String str) {
		Automaton automaton = new Automaton();
		for (char c : str.toCharArray())
			automaton.get(c);
		return (int) (automaton.result * automaton.sign);
	}


}

class Solution {
	public int myAtoi(String str) {
		// 删除前导空格
		str = str.trim();
		if (str.length() == 0) return 0;
		// 判断第一个字符是否为符号或数字，如果都不是则直接剪枝
		if (!Character.isDigit(str.charAt(0))
			&& str.charAt(0) != '-' && str.charAt(0) != '+')
			return 0;
		// 使用 long 类型存储，因为数字会越界
		long ans = 0L;
		boolean neg = str.charAt(0) == '-'; // 获取符号
		// 数字的起始位置
		int i = !Character.isDigit(str.charAt(0)) ? 1 : 0;
		while (i < str.length() && Character.isDigit(str.charAt(i))) {
			// 添加到结果
			ans = ans * 10 + (str.charAt(i++) - '0');
			// 判断是否越界
			if (!neg && ans > Integer.MAX_VALUE) {
				ans = Integer.MAX_VALUE;
				break;
			}
			if (neg && ans > 1L + Integer.MAX_VALUE) {
				ans = 1L + Integer.MAX_VALUE;
				break;
			}
		}
		return neg ? (int) -ans : (int) ans;
	}
}